<!-- build time: Tue Aug 15 2023 11:55:16 GMT+0800 (中国标准时间) --><!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#FFF"><link rel="apple-touch-icon" sizes="180x180" href="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/images/apple-touch-icon.png"><link rel="icon" type="image/ico" sizes="32x32" href="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/images/favicon.ico"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><link rel="alternate" type="application/rss+xml" href="http://zero-yuan.gitee.io/rss.xml"><link rel="alternate" type="application/atom+xml" href="http://zero-yuan.gitee.io/atom.xml"><link rel="alternate" type="application/json" href="http://zero-yuan.gitee.io/feed.json"><link rel="stylesheet" href="//fonts.googleapis.com/css?family=Mulish:300,300italic,400,400italic,700,700italic%7CFredericka%20the%20Great:300,300italic,400,400italic,700,700italic%7CNoto%20Serif%20JP:300,300italic,400,400italic,700,700italic%7CNoto%20Serif%20SC:300,300italic,400,400italic,700,700italic%7CInconsolata:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext"><link rel="stylesheet" href="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/css/app.css?v=0.2.5"><meta name="keywords" content="Java基础"><link rel="canonical" href="http://zero-yuan.gitee.io/interview/Java%E9%9B%86%E5%90%88%E7%9B%B8%E5%85%B3%E9%9D%A2%E8%AF%95%E9%A2%98/"><title>Java集合相关面试题 - 面经 | 智慧笔记 = = 欢迎来到智慧笔记~这里主要会记录编程学习笔记🌸</title><meta name="generator" content="Hexo 6.3.0"></head><body itemscope itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">Java集合相关面试题</h1><div class="meta"><span class="item" title="创建时间：2023-08-13 00:00:00"><span class="icon"><i class="ic i-calendar"></i> </span><span class="text">发表于</span> <time itemprop="dateCreated datePublished" datetime="2023-08-13T00:00:00+08:00">2023-08-13</time> </span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i> </span><span class="text">本文字数</span> <span>20k</span> <span class="text">字</span> </span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i> </span><span class="text">阅读时长</span> <span>18 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span> <span class="line"></span> <span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">智慧笔记</a></li></ul><ul class="right"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div id="imgs" class="pjax"><img src="https://tse2-mm.cn.bing.net/th/id/OIP-C.UKWDjDgUDHOPDzdN5UDFlQHaDc?w=349&h=162&c=7&r=0&o=5&dpr=1.3&pid=1.7"></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"/></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"/><use xlink:href="#gentle-wave" x="48" y="3"/><use xlink:href="#gentle-wave" x="48" y="5"/><use xlink:href="#gentle-wave" x="48" y="7"/></g></svg></div><main><div class="inner"><div id="main" class="pjax"><div class="article wrap"><div class="breadcrumb" itemscope itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i> <span><a href="/">首页</a></span><i class="ic i-angle-right"></i> <span class="current" itemprop="itemListElement" itemscope itemtype="https://schema.org/ListItem"><a href="/categories/interview/" itemprop="item" rel="index" title="分类于 面经"><span itemprop="name">面经</span></a><meta itemprop="position" content="1"></span></div><article itemscope itemtype="http://schema.org/Article" class="post block" lang="zh-CN"><link itemprop="mainEntityOfPage" href="http://zero-yuan.gitee.io/interview/Java%E9%9B%86%E5%90%88%E7%9B%B8%E5%85%B3%E9%9D%A2%E8%AF%95%E9%A2%98/"><span hidden itemprop="author" itemscope itemtype="http://schema.org/Person"><meta itemprop="image" content="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/images/avatar.webp"><meta itemprop="name" content="anoxia"><meta itemprop="description" content="欢迎来到智慧笔记~这里主要会记录编程学习笔记🌸, anoxia的后端博客"></span><span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization"><meta itemprop="name" content=""></span><div class="body md" itemprop="articleBody"><h2 id="前言"><a class="anchor" href="#前言">#</a> 前言</h2><p>这次课程主要涉及到的是 List 和 Map 相关的面试题，比较高频就是</p><ul><li><p>ArrayList</p></li><li><p>LinkedList</p></li><li><p>HashMap</p></li><li><p>ConcurrentHashMap</p></li></ul><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427162524322.png" alt=""></p><ul><li>ArrayList 底层实现是数组</li><li>LinkedList 底层实现是双向链表</li><li>HashMap 的底层实现使用了众多数据结构，包含了数组、链表、散列表、红黑树等</li></ul><p>在讲解这些集合之后，我们会讲解数据结构，知道了数据结构的特点之后，熟悉集合就更加简单了。在讲解数据结构之前，我们也会简单普及一下算法复杂度分析，让大家能够评判代码的好坏，也能更加深入去理解数据结构和集合。</p><h2 id="1-算法复杂度分析"><a class="anchor" href="#1-算法复杂度分析">#</a> 1 算法复杂度分析</h2><h3 id="11-为什么要进行复杂度分析"><a class="anchor" href="#11-为什么要进行复杂度分析">#</a> 1.1 为什么要进行复杂度分析？</h3><p>我们先来看下面这个代码，你能评判这个代码的好坏吗？</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token comment">/**</span></pre></td></tr><tr><td data-num="2"></td><td><pre> ** * 求 **1~n** 的累加和</pre></td></tr><tr><td data-num="3"></td><td><pre> ** @param* *n</pre></td></tr><tr><td data-num="4"></td><td><pre> ** @return</pre></td></tr><tr><td data-num="5"></td><td><pre>*/</pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">sum</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>   <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>   <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>     sum <span class="token operator">=</span> sum <span class="token operator">+</span> i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre>   <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="11"></td><td><pre>   <span class="token keyword">return</span> sum<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>其实学习算法复杂度的好处就是：</p><ul><li><p>指导你编写出性能更优的代码</p></li><li><p>评判别人写的代码的好坏</p></li></ul><blockquote><p>相信你学完了算法复杂度分析，就有能力评判上面代码的好坏了</p></blockquote><p>关于算法复杂度分析，包含了两个内容，一个是时间复杂度，一个是空间复杂度，通常情况下说复杂度，都是指时间复杂度，我们也会重点讲解时间复杂度</p><h3 id="12-时间复杂度"><a class="anchor" href="#12-时间复杂度">#</a> 1.2 时间复杂度</h3><h4 id="121-案例"><a class="anchor" href="#121-案例">#</a> 1.2.1 案例</h4><p>时间复杂度分析：简单来说就是评估代码的执行耗时的，大家还是看刚才的代码：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token comment">/**</span></pre></td></tr><tr><td data-num="2"></td><td><pre> ** * 求 **1~n** 的累加和</pre></td></tr><tr><td data-num="3"></td><td><pre> ** @param* *n</pre></td></tr><tr><td data-num="4"></td><td><pre> ** @return</pre></td></tr><tr><td data-num="5"></td><td><pre>*/</pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">sum</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>   <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>   <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>     sum <span class="token operator">=</span> sum <span class="token operator">+</span> i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre>   <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="11"></td><td><pre>   <span class="token keyword">return</span> sum<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>分析这个代码的时间复杂度，分析过程如下：</p><p>1. 假如每行代码的执行耗时一样：1ms</p><p>2. 分析这段代码总执行多少行？3n+3</p><p>3. 代码耗时总时间： T (n) = (3n + 3) * 1ms</p><blockquote><p>T (n): 就是代码总耗时</p></blockquote><p>我们现在有了总耗时，需要借助大 O 表示法来计算这个代码的时间复杂度</p><h4 id="122-大o表示法"><a class="anchor" href="#122-大o表示法">#</a> 1.2.2 大 O 表示法</h4><p><strong>大 O 表示法</strong>：不具体表示代码真正的执行时间，而是表示<strong>代码执行时间随数据规模增长的变化趋势</strong>。</p><p>刚才的代码示例总耗时公式为：T (n) = (3n + 3) * 1ms</p><blockquote><p>其中 (3n + 3) 是代码的总行数，每行执行的时间都一样，所以得出结论：</p><p><strong>T (n) 与代码的执行次数成正比 (代码行数越多，执行时间越长)</strong></p></blockquote><p>不过，大 O 表示法只需要代码执行时间与数据规模的增长趋势，公式可以简化如下：</p><p>T(n) =O(3n + 3)------------&gt; T(n) = O(n)</p><blockquote><p>当 n 很大时，公式中的低阶，常量，系数三部分并不左右其增长趋势，因此可以忽略，我们只需要记录一个最大的量级就可以了</p></blockquote><p>下图也能表明数据的趋势</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427173120668.png" alt="image-20230427173120668"></p><h4 id="123-常见复杂度表示形式"><a class="anchor" href="#123-常见复杂度表示形式">#</a> 1.2.3 常见复杂度表示形式</h4><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427173742389.png" alt="image-20230427173742389"></p><p>速记口诀：<strong>常对幂指阶</strong></p><p>越在上面的性能就越高，越往下性能就越低</p><p>下图是一些比较常见时间复杂度的时间与数据规模的趋势：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427173937663.png" alt="image-20230427173937663"></p><h4 id="124-时间复杂度o1"><a class="anchor" href="#124-时间复杂度o1">#</a> 1.2.4 时间复杂度 O (1)</h4><p>实例代码：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">test01</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>    <span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>    <span class="token keyword">return</span> i<span class="token operator">+</span>j<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>代码只有三行，它的复杂度也是 O (1)，而不是 O (3)</p><p>再看如下代码：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">test02</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>    <span class="token keyword">int</span> sum<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">100</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="5"></td><td><pre>        sum <span class="token operator">=</span> sum<span class="token operator">+</span>i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>sum<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>整个代码中因为循环次数是固定的就是 100 次，这样的代码复杂度我们认为也是 O (1)</p><p>一句话总结：<strong>只要代码的执行时间不随着 n 的增大而增大，这样的代码复杂度都是 O (1)</strong></p><h4 id="125-时间复杂度on"><a class="anchor" href="#125-时间复杂度on">#</a> 1.2.5 时间复杂度 O (n)</h4><p>实例代码 1：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token comment">/**</span></pre></td></tr><tr><td data-num="2"></td><td><pre> * 求 1~n 的累加和</pre></td></tr><tr><td data-num="3"></td><td><pre> * @param n</pre></td></tr><tr><td data-num="4"></td><td><pre> * @return</pre></td></tr><tr><td data-num="5"></td><td><pre> */</pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">sum</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>    <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>    <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>        sum <span class="token operator">=</span> sum <span class="token operator">+</span> i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="11"></td><td><pre>    <span class="token keyword">return</span> sum<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>一层 for 循序时间复杂度就是 O (n)</p><p>实例代码 2：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">int</span> <span class="token function">sum2</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="5"></td><td><pre>            sum <span class="token operator">=</span> sum <span class="token operator">+</span> i <span class="token operator">*</span> j<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>    <span class="token keyword">return</span> sum<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>这个代码的执行行数为：O (3n^2 + 3n + 3)，不过，依据大 O 表示的规则：<strong>常量、系数、低阶，可以忽略</strong></p><p>所以这个代码最终的时间复杂度为：O (n^2)</p><h4 id="126-时间复杂度ologn"><a class="anchor" href="#126-时间复杂度ologn">#</a> 1.2.6 时间复杂度 O (logn)</h4><p>对数复杂度非常的常见，但相对比较难以分析，实例代码：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">test04</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>    <span class="token keyword">while</span><span class="token punctuation">(</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>        i <span class="token operator">=</span> i <span class="token operator">*</span> <span class="token number">2</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>分析这个代码的复杂度，我们必须要再强调一个前提：<strong>复杂度分析就是要弄清楚代码的执行次数和数据规模 n 之间的关系</strong></p><p>以上代码最关键的一行是： <code>i = i * 2</code> ，这行代码可以决定这个 while 循环执行代码的行数， <code>i</code> 的值是可以无限接近 <code>n</code> 的值的。如果 <code>i</code> 一旦大于等于了 <code>n</code> 则循环条件就不满足了。也就说达到了最大的行数。我们可以分析一下 <code>i</code> 这个值变化的过程</p><p>分析过程如下：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427174832858.png" alt="image-20230427174832858"></p><p>由此可知，代码的时间复杂度表示为 O (log n)</p><h4 id="127-时间复杂度on-log-n"><a class="anchor" href="#127-时间复杂度on-log-n">#</a> 1.2.7 时间复杂度 O (n * log n)</h4><p>分析完 O (log n)，那 O ( n * log n ) 就很容易理解了，比如下列代码：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">test05</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>        <span class="token function">test04</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="7"></td><td><pre></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">test04</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>    <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre>    <span class="token keyword">while</span><span class="token punctuation">(</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="11"></td><td><pre>        i <span class="token operator">=</span> i <span class="token operator">*</span> <span class="token number">2</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="13"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><h3 id="13-空间复杂度"><a class="anchor" href="#13-空间复杂度">#</a> 1.3 空间复杂度</h3><p>空间复杂度全称是渐进空间复杂度，表示算法占用的额外<strong>存储空间</strong>与<strong>数据规模</strong>之间的增长关系</p><p>看下面代码</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">test</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>    <span class="token keyword">int</span> sum<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="5"></td><td><pre>        sum <span class="token operator">=</span> sum<span class="token operator">+</span>i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>sum<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>代码执行并不需要占用额外的存储空间，只需要常量级的内存空间大小，因此空间复杂度是 O (1)</p><p>再来看一个其他例子：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">void</span> <span class="token function">print</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>    <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> a <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>    <span class="token keyword">for</span> <span class="token punctuation">(</span>i<span class="token punctuation">;</span> i <span class="token operator">&lt;</span>n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="5"></td><td><pre>        a<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i <span class="token operator">*</span> i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>    <span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token operator">--</span>i<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>传入一个变量 n，决定申请多少的 int 数组空间内存，此段代码的空间复杂度为 O (n)</p><p>我们常见的空间复杂度就是 O (1),O (n),O (n ^2)，其他像对数阶的复杂度几乎用不到，因此空间复杂度比时间复杂度分析要简单的多。</p><h2 id="2-list相关面试题"><a class="anchor" href="#2-list相关面试题">#</a> 2 List 相关面试题</h2><h3 id="21-数组"><a class="anchor" href="#21-数组">#</a> 2.1 数组</h3><h4 id="211-数组概述"><a class="anchor" href="#211-数组概述">#</a> 2.1.1 数组概述</h4><p>数组（Array）是一种用<strong>连续的内存空间</strong>存储<strong>相同数据类型</strong>数据的线性数据结构。</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> array <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token number">22</span><span class="token punctuation">,</span><span class="token number">33</span><span class="token punctuation">,</span><span class="token number">88</span><span class="token punctuation">,</span><span class="token number">66</span><span class="token punctuation">,</span><span class="token number">55</span><span class="token punctuation">,</span><span class="token number">25</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span></pre></td></tr></table></figure><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427175545402.png" alt="image-20230427175545402"></p><p>我们定义了这么一个数组之后，在内存的表示是这样的：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427175633253.png" alt="image-20230427175633253"></p><p>现在假如，我们通过 <code>arrar[1]</code> ，想要获得下标为 1 这个元素，但是现在栈内存中指向的堆内存数组的首地址，它是如何获取下标为 1 这个数据的？</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427175849493.png" alt="image-20230427175849493"></p><h4 id="212-寻址公式"><a class="anchor" href="#212-寻址公式">#</a> 2.1.2 寻址公式</h4><p>为了方便大家理解，我们把数组的内存地址稍微改了一下，都改成了数字，如下图</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427180056509.png" alt="image-20230427180056509"></p><p>在数组在内存中查找元素的时候，是有一个寻址公式的，如下：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> baseAddress <span class="token operator">+</span> i <span class="token operator">*</span> dataTypeSize</pre></td></tr></table></figure><blockquote><p>baseAddress：数组的首地址，目前是 10</p><p>dataTypeSize：代表数组中元素类型的大小，目前数组重存储的是 int 型的数据，dataTypeSize=4 个字节</p><p>arr：指的是数组</p><p>i：指的是数组的下标</p></blockquote><p>有了寻址公式以后，我们再来获取一下下标为 1 的元素，这个是原来的数组</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> array <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token number">22</span><span class="token punctuation">,</span><span class="token number">33</span><span class="token punctuation">,</span><span class="token number">88</span><span class="token punctuation">,</span><span class="token number">66</span><span class="token punctuation">,</span><span class="token number">55</span><span class="token punctuation">,</span><span class="token number">25</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span></pre></td></tr></table></figure><p>套入公式：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre>array<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span><span class="token number">10</span> <span class="token operator">+</span> i <span class="token operator">*</span> <span class="token number">4</span> <span class="token operator">=</span> <span class="token number">14</span></pre></td></tr></table></figure><p>获取到 14 这个地址，就能获取到下标为 1 的这个元素了。</p><h4 id="213-操作数组的时间复杂度"><a class="anchor" href="#213-操作数组的时间复杂度">#</a> 2.1.3 操作数组的时间复杂度</h4><p><strong>1. 随机查询 (根据索引查询)</strong></p><p>数组元素的访问是通过下标来访问的，计算机通过数组的<strong>首地址</strong>和<strong>寻址公式</strong>能够很快速的找到想要访问的元素</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">test01</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> a<span class="token punctuation">,</span><span class="token keyword">int</span> i<span class="token punctuation">)</span><span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>   <span class="token keyword">return</span> a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>   <span class="token comment">// a[i] = baseAddress + i \* dataSize</span></pre></td></tr><tr><td data-num="4"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><p>代码的执行次数并不会随着数组的数据规模大小变化而变化，是常数级的，所以查询数据操作的时间复杂度是 O (1)</p><p><strong>2. 未知索引查询 O (n) 或 O (log2n)</strong></p><p>情况一：查找数组内的元素，查找 55 号数据，遍历数组时间复杂度为 O (n)</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20221007101831281.png" alt="image-20221007101831281"></p><p>情况二：查找排序后数组内的元素，通过二分查找算法查找 55 号数据时间复杂度为 O (logn)</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20221007101811885.png" alt="image-20221007101811885"></p><p><strong>3. 插入 O (n)</strong></p><p>数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低。</p><p>假设数组的长度为 n，现在如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。如下图所示：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20220820104903422.png" alt="image-20220820104903422"></p><p>新增之后的数据变化，如下</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20220820104950846.png" alt="image-20220820104950846"></p><p>所以：</p><p>插入操作，最好情况下是 O (1) 的，最坏情况下是 O (n) 的，<strong>平均情况下的时间复杂度是 O (n)</strong>。</p><p><strong>4. 删除 O (n)</strong></p><p>同理可得：如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了，时间复杂度仍然是 O (n)。</p><h3 id="22-arraylist源码分析"><a class="anchor" href="#22-arraylist源码分析">#</a> 2.2 ArrayList 源码分析</h3><p>分析 ArrayList 源码主要从三个方面去翻阅：成员变量，构造函数，关键方法</p><blockquote><p>以下源码都来源于 jdk1.8</p></blockquote><h4 id="221-成员变量"><a class="anchor" href="#221-成员变量">#</a> 2.2.1 成员变量</h4><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427192118259.png" alt="image-20230427192118259"></p><blockquote><p><em>DEFAULT_CAPACITY</em> = 10; 默认初始的容量 **(CAPACITY)</p><p><em>EMPTY_ELEMENTDATA</em> = {}; 用于空实例的共享空数组实例</p><p><em>DEFAULTCAPACITY_EMPTY_ELEMENTDATA</em> = {}; 用于默认大小的空实例的共享空数组实例</p><p>Object [] elementData; 存储元素的数组缓冲区</p><p>int size; ArrayList 的大小（它包含的元素数量）</p></blockquote><h4 id="222-构造方法"><a class="anchor" href="#222-构造方法">#</a> 2.2.2 构造方法</h4><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427192154014.png" alt="image-20230427192154014"></p><blockquote><ul><li><p>第一个构造是带初始化容量的构造函数，可以按照指定的容量初始化数组</p></li><li><p>第二个是无参构造函数，默认创建一个空集合</p></li></ul></blockquote><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427192200918.png" alt="image-20230427192200918"></p><blockquote><p>将 collection 对象转换成数组，然后将数组的地址的赋给 elementData</p></blockquote><h4 id="223-arraylist源码分析"><a class="anchor" href="#223-arraylist源码分析">#</a> 2.2.3 ArrayList 源码分析</h4><p>添加数据的流程</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230427192644244.png" alt="image-20230427192644244"></p><p><strong>结论：</strong></p><ul><li>底层数据结构</li></ul><p>ArrayList 底层是用动态的数组实现的</p><ul><li>初始容量</li></ul><p>ArrayList 初始容量为 0，当第一次添加数据的时候才会初始化容量为 10</p><ul><li>扩容逻辑</li></ul><p>ArrayList 在进行扩容的时候是原来容量的 1.5 倍，每次扩容都需要拷贝数组</p><ul><li><p>添加逻辑</p><ul><li><p>确保数组已使用长度（size）加 1 之后足够存下下一个数据</p></li><li><p>计算数组的容量，如果当前数组已使用长度 + 1 后的大于当前的数组长度，则调用 grow 方法扩容（原来的 1.5 倍）</p></li><li><p>确保新增的数据有地方存储之后，则将新元素添加到位于 size 的位置上。</p></li><li><p>返回添加成功布尔值。</p></li></ul></li></ul><h4 id="224-面试题-arraylist-listnew-arraylist10中的list扩容几次"><a class="anchor" href="#224-面试题-arraylist-listnew-arraylist10中的list扩容几次">#</a> 2.2.4 面试题 - ArrayList list=new ArrayList (10) 中的 list 扩容几次</h4><blockquote><p>难易程度：☆☆☆</p><p>出现频率：☆☆</p></blockquote><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428185505677.png" alt="image-20230428185505677"></p><p>参考回答：</p><p>该语句只是声明和实例了一个 ArrayList，指定了容量为 10，未扩容</p><h4 id="224-面试题-如何实现数组和list之间的转换"><a class="anchor" href="#224-面试题-如何实现数组和list之间的转换">#</a> 2.2.4 面试题 - 如何实现数组和 List 之间的转换</h4><blockquote><p>难易程度：☆☆☆</p><p>出现频率：☆☆</p></blockquote><p>如下代码：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428185600918.png" alt="image-20230428185600918"></p><p>参考回答：</p><ul><li><p>数组转 List ，使用 JDK 中 java.util.Arrays 工具类的 asList 方法</p></li><li><p>List 转数组，使用 List 的 toArray 方法。无参 toArray 方法返回 Object 数组，传入初始化长度的数组对象，返回该对象数组</p></li></ul><p>面试官再问：</p><p>1，用 Arrays.asList 转 List 后，如果修改了数组内容，list 受影响吗</p><p>2，List 用 toArray 转数组后，如果修改了 List 内容，数组受影响吗</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428185657791.png" alt="image-20230428185657791"></p><blockquote><p>数组转 List 受影响</p><p>List 转数组不受影响</p></blockquote><p>再答：</p><p>1，用 Arrays.asList 转 List 后，如果修改了数组内容，list 受影响吗</p><p>Arrays.asList 转换 list 之后，如果修改了数组的内容，list 会受影响，因为它的底层使用的 Arrays 类中的一个内部类 ArrayList 来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址</p><p>2，List 用 toArray 转数组后，如果修改了 List 内容，数组受影响吗</p><p>list 用了 toArray 转数组后，如果修改了 list 内容，数组不会影响，当调用了 toArray 以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使 list 修改了以后，数组也不受影响</p><h3 id="23-链表"><a class="anchor" href="#23-链表">#</a> 2.3 链表</h3><h4 id="231-单向链表"><a class="anchor" href="#231-单向链表">#</a> 2.3.1 单向链表</h4><ul><li><p>链表中的每一个元素称之为结点（Node）</p></li><li><p>物理存储单元上，非连续、非顺序的存储结构</p></li><li><p>单向链表：每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next</p></li></ul><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428185922776.png" alt="image-20230428185922776"></p><p>代码实现参考：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428185945929.png" alt="image-20230428185945929"></p><p>链表中的某个节点为 B，B 的下一个节点为 C 表示： B.next==C</p><h4 id="232-单向链表时间复杂度分析"><a class="anchor" href="#232-单向链表时间复杂度分析">#</a> 2.3.2 单向链表时间复杂度分析</h4><p>（1）查询操作</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428190130901.png" alt="image-20230428190130901"></p><ul><li><p>只有在查询头节点的时候不需要遍历链表，时间复杂度是 O (1)</p></li><li><p>查询其他结点需要遍历链表，时间复杂度是 O (n)</p></li></ul><p>（2）插入和删除操作</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428190210915.png" alt="image-20230428190210915"></p><ul><li>只有在添加和删除头节点的时候不需要遍历链表，时间复杂度是 O (1)</li><li>添加或删除其他结点需要遍历链表找到对应节点后，才能完成新增或删除节点，时间复杂度是 O (n)</li></ul><h4 id="233-双向链表"><a class="anchor" href="#233-双向链表">#</a> 2.3.3 双向链表</h4><p>而双向链表，顾名思义，它支持两个方向</p><ul><li><p>每个结点不止有一个后继指针 next 指向后面的结点</p></li><li><p>有一个前驱指针 prev 指向前面的结点</p></li></ul><p>参考代码</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428190324752.png" alt="image-20230428190324752"></p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428190353286.png" alt="image-20230428190353286"></p><p>对比单链表：</p><ul><li><p>双向链表需要额外的两个空间来存储后继结点和前驱结点的地址</p></li><li><p>支持双向遍历，这样也带来了双向链表操作的灵活性</p></li></ul><h4 id="234-双向链表时间复杂度分析"><a class="anchor" href="#234-双向链表时间复杂度分析">#</a> 2.3.4 双向链表时间复杂度分析</h4><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428190450517.png" alt="image-20230428190450517"></p><p>（1）查询操作</p><ul><li><p>查询头尾结点的时间复杂度是 O (1)</p></li><li><p>平均的查询时间复杂度是 O (n)</p></li><li><p>给定节点找前驱节点的时间复杂度为 O (1)</p></li></ul><p>（2）增删操作</p><ul><li><p>头尾结点增删的时间复杂度为 O (1)</p></li><li><p>其他部分结点增删的时间复杂度是 O (n)</p></li><li><p>给定节点增删的时间复杂度为 O (1)</p></li></ul><h4 id="235-面试题-arraylist和linkedlist的区别是什么"><a class="anchor" href="#235-面试题-arraylist和linkedlist的区别是什么">#</a> 2.3.5 面试题 - ArrayList 和 LinkedList 的区别是什么？</h4><ul><li><p>底层数据结构</p><ul><li><p>ArrayList 是动态数组的数据结构实现</p></li><li><p>LinkedList 是双向链表的数据结构实现</p></li></ul></li><li><p>操作数据效率</p><ul><li>ArrayList 按照下标查询的时间复杂度 O (1)【内存是连续的，根据寻址公式】， LinkedList 不支持下标查询</li><li>查找（未知索引）： ArrayList 需要遍历，链表也需要链表，时间复杂度都是 O (n)</li><li>新增和删除<ul><li>ArrayList 尾部插入和删除，时间复杂度是 O (1)；其他部分增删需要挪动数组，时间复杂度是 O (n)</li><li>LinkedList 头尾节点增删时间复杂度是 O (1)，其他都需要遍历链表，时间复杂度是 O (n)</li></ul></li></ul></li><li><p>内存空间占用</p><ul><li><p>ArrayList 底层是数组，内存连续，节省内存</p></li><li><p>LinkedList 是双向链表需要存储数据，和两个指针，更占用内存</p></li></ul></li><li><p>线程安全</p><ul><li>ArrayList 和 LinkedList 都不是线程安全的</li><li>如果需要保证线程安全，有两种方案：<ul><li>在方法内使用，局部变量则是线程安全的</li><li>使用线程安全的 ArrayList 和 LinkedList</li></ul></li></ul></li></ul><h2 id="3-hashmap相关面试题"><a class="anchor" href="#3-hashmap相关面试题">#</a> 3 HashMap 相关面试题</h2><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428194715016.png" alt="image-20230428194715016"></p><h3 id="31-二叉树"><a class="anchor" href="#31-二叉树">#</a> 3.1 二叉树</h3><h4 id="311-二叉树概述"><a class="anchor" href="#311-二叉树概述">#</a> 3.1.1 二叉树概述</h4><p>二叉树，顾名思义，每个节点最多有两个 “叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。</p><p>二叉树每个节点的左子树和右子树也分别满足二叉树的定义。</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428194831426.png" alt="image-20230428194831426"></p><p>Java 中有两个方式实现二叉树：数组存储，链式存储。</p><p>基于链式存储的树的节点可定义如下：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428194904383.png" alt="image-20230428194904383"></p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428194931132.png" alt="image-20230428194931132"></p><h4 id="312-二叉搜索树"><a class="anchor" href="#312-二叉搜索树">#</a> 3.1.2 二叉搜索树</h4><p>在二叉树中，比较常见的二叉树有：</p><ul><li><p>满二叉树</p></li><li><p>完全二叉树</p></li><li><p><strong>二叉搜索树</strong></p></li><li><p><strong>红黑树</strong></p></li></ul><p>我们重点讲解二叉搜索树和红黑树</p><p>（1）二叉搜索树概述</p><p>二叉搜索树 (Binary Search Tree,BST) 又名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型</p><p>二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428195206422.png" alt="image-20230428195206422"></p><p>（2）二叉搜索树 - 时间复杂度分析</p><p>实际上由于二叉查找树的形态各异，时间复杂度也不尽相同，我画了几棵树我们来看一下插入，查找，删除的时间复杂度</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428195341917.png" alt="image-20230428195341917"></p><p>插入，查找，删除的时间复杂度<strong> O (logn)</strong></p><p>极端情况下二叉搜索的时间复杂度</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428195449799.png" alt="image-20230428195449799"></p><p>对于图中这种情况属于最坏的情况，二叉查找树已经退化成了链表，左右子树极度不平衡，此时查找的时间复杂度肯定是 O (n)。</p><h4 id="313-红黑树"><a class="anchor" href="#313-红黑树">#</a> 3.1.3 红黑树</h4><p>（1）概述</p><p><strong>红黑树（Red Black Tree）</strong>：也是一种自平衡的二叉搜索树 (BST)，之前叫做平衡二叉 B 树（Symmetric Binary B-Tree）</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428195832724.png" alt="image-20230428195832724"></p><p>（2）红黑树的特质</p><p>性质 1：节点要么是<strong>红色</strong>，要么是<strong>黑色</strong></p><p>性质 2：根节点是<strong>黑色</strong></p><p>性质 3：叶子节点都是黑色的空节点</p><p>性质 4：红黑树中红色节点的子节点都是黑色</p><p>性质 5：从任一节点到叶子节点的所有路径都包含相同数目的黑色节点</p><p><strong>在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质，保证红黑树的平衡</strong></p><p>（3）红黑树的复杂度</p><ul><li><p>查找：</p><ul><li>红黑树也是一棵 BST（二叉搜索树）树，查找操作的时间复杂度为：O (log n)</li></ul></li><li><p>添加：</p><ul><li>添加先要从根节点开始找到元素添加的位置，时间复杂度 O (log n)</li><li>添加完成后涉及到复杂度为 O (1) 的旋转调整操作</li><li>故整体复杂度为：O (log n)</li></ul></li><li><p>删除：</p><ul><li>首先从根节点开始找到被删除元素的位置，时间复杂度 O (log n)</li><li>删除完成后涉及到复杂度为 O (1) 的旋转调整操作</li><li>故整体复杂度为：O (log n)</li></ul></li></ul><h3 id="32-散列表"><a class="anchor" href="#32-散列表">#</a> 3.2 散列表</h3><p>在 HashMap 中的最重要的一个数据结构就是散列表，在散列表中又使用到了红黑树和链表</p><h4 id="321-散列表hash-table概述"><a class="anchor" href="#321-散列表hash-table概述">#</a> 3.2.1 散列表（Hash Table）概述</h4><p>散列表 (Hash Table) 又名哈希表 / Hash 表，是根据键（Key）直接访问在内存存储位置值（Value）的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性</p><p>举个例子：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428200919454.png" alt="image-20230428200919454"></p><p>假设有 100 个人参加马拉松，编号是 1-100，如果要编程实现根据选手的编号迅速找到选手信息？</p><p>可以把选手信息存入数组中，选手编号就是数组的下标，数组的元素就是选手的信息。</p><p>当我们查询选手信息的时候，只需要根据选手的编号到数组中查询对应的元素就可以快速找到选手的信息，如下图：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428201000814.png" alt="image-20230428201000814"></p><p>现在需求升级了：</p><p>假设有 100 个人参加马拉松，不采用 1-100 的自然数对选手进行编号，编号有一定的规则比如：2023ZHBJ001，其中 2023 代表年份，ZH 代表中国，BJ 代表北京，001 代表原来的编号，那此时的编号 2023ZHBJ001 不能直接作为数组的下标，此时应该如何实现呢？</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428201321607.png" alt="image-20230428201321607"></p><p>我们目前是把选手的信息存入到数组中，不过选手的编号不能直接作为数组的下标，不过，可以把选手的选号进行转换，转换为数值就可以继续作为数组的下标了？</p><p>转换可以使用散列函数进行转换</p><h4 id="322-散列函数和散列冲突"><a class="anchor" href="#322-散列函数和散列冲突">#</a> 3.2.2 散列函数和散列冲突</h4><p>将键 (key) 映射为数组下标的函数叫做散列函数。可以表示为：hashValue = hash (key)</p><p>散列函数的基本要求：</p><ul><li><p>散列函数计算得到的散列值必须是大于等于 0 的正整数，因为 hashValue 需要作为数组的下标。</p></li><li><p>如果 key1==key2，那么经过 hash 后得到的哈希值也必相同即：hash (key1) == hash (key2）</p></li><li><p><strong>如果 key1 != key2，那么经过 hash 后得到的哈希值也必不相同即：hash (key1) != hash (key2)</strong></p></li></ul><p>实际的情况下想找一个散列函数能够做到对于不同的 key 计算得到的散列值都不同几乎是不可能的，即便像著名的 MD5,SHA 等哈希算法也无法避免这一情况，这就是散列冲突 (或者哈希冲突，哈希碰撞，<strong>就是指多个 key 映射到同一个数组下标位置</strong>)</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428203219225.png" alt="image-20230428203219225"></p><h4 id="323-散列冲突-链表法拉链"><a class="anchor" href="#323-散列冲突-链表法拉链">#</a> 3.2.3 散列冲突 - 链表法（拉链）</h4><p>在散列表中，数组的每个下标位置我们可以称之为桶（bucket）或者槽（slot），每个桶 (槽) 会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428203437910.png" alt="image-20230428203437910"></p><p>简单就是，如果有多个 key 最终的 hash 值是一样的，就会存入数组的同一个下标中，下标中挂一个链表存入多个数据</p><h4 id="324-时间复杂度-散列表"><a class="anchor" href="#324-时间复杂度-散列表">#</a> 3.2.4 时间复杂度 - 散列表</h4><p>1，插入操作，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是 O (1)</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428203711269.png" alt="image-20230428203711269"></p><blockquote><p>通过计算就可以找到元素</p></blockquote><p>2，当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除</p><ul><li><p>平均情况下基于链表法解决冲突时查询的时间复杂度是 O (1)</p></li><li><p>散列表可能会退化为链表，查询的时间复杂度就从 O (1) 退化为 O (n)</p></li></ul><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428203858903.png" alt="image-20230428203858903"></p><ul><li>将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，查询的时间复杂度是 O (logn)</li></ul><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428203924816.png" alt="image-20230428203924816"></p><p>将链表法中的链表改造红黑树还有一个非常重要的原因，可以防止 DDos 攻击</p><blockquote><p>DDos 攻击:</p><p>分布式拒绝服务攻击 (英文意思是 Distributed Denial of Service，简称 DDoS）</p><p>指处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个</p></blockquote><h3 id="33-面试题-说一下hashmap的实现原理"><a class="anchor" href="#33-面试题-说一下hashmap的实现原理">#</a> 3.3 面试题 - 说一下 HashMap 的实现原理？</h3><p>HashMap 的数据结构： 底层使用 hash 表数据结构，即数组和链表或红黑树</p><ol><li><p>当我们往 HashMap 中 put 元素时，利用 key 的 hashCode 重新 hash 计算出当前对象的元素在数组中的下标</p></li><li><p>存储时，如果出现 hash 值相同的 key，此时有两种情况。</p></li></ol><p>a. 如果 key 相同，则覆盖原始值；</p><p>b. 如果 key 不同（出现冲突），则将当前的 key-value 放入链表或红黑树中</p><ol start="3"><li>获取时，直接找到 hash 值对应的下标，在进一步判断 key 是否相同，从而找到对应值。</li></ol><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428204902016.png" alt="image-20230428204902016"></p><p>面试官追问：HashMap 的 jdk1.7 和 jdk1.8 有什么区别</p><ul><li><p>JDK1.8 之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。</p></li><li><p>jdk1.8 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8） 时并且数组长度达到 64 时，将链表转化为红黑树，以减少搜索时间。扩容 resize ( ) 时，红黑树拆分成的树的结点数小于等于临界值 6 个，则退化成链表</p></li></ul><h3 id="34-面试题-hashmap的put方法的具体流程"><a class="anchor" href="#34-面试题-hashmap的put方法的具体流程">#</a> 3.4 面试题 - HashMap 的 put 方法的具体流程</h3><h4 id="341-hashmap常见属性"><a class="anchor" href="#341-hashmap常见属性">#</a> 3.4.1 hashMap 常见属性</h4><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428210404117.png" alt="image-20230428210404117"></p><h4 id="342-源码分析"><a class="anchor" href="#342-源码分析">#</a> 3.4.2 源码分析</h4><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428210450744.png" alt="image-20230428210450744"></p><ul><li><p>HashMap 是懒惰加载，在创建对象时并没有初始化数组</p></li><li><p>在无参的构造函数中，设置了默认的加载因子是 0.75</p></li></ul><p>添加数据流程图</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428210624847.png" alt="image-20230428210624847"></p><p>具体的源码：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token keyword">public</span> <span class="token class-name">V</span> <span class="token function">put</span><span class="token punctuation">(</span><span class="token class-name">K</span> key<span class="token punctuation">,</span> <span class="token class-name">V</span> value<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>    <span class="token keyword">return</span> <span class="token function">putVal</span><span class="token punctuation">(</span><span class="token function">hash</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> <span class="token boolean">false</span><span class="token punctuation">,</span> <span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="4"></td><td><pre></pre></td></tr><tr><td data-num="5"></td><td><pre><span class="token keyword">final</span> <span class="token class-name">V</span> <span class="token function">putVal</span><span class="token punctuation">(</span><span class="token keyword">int</span> hash<span class="token punctuation">,</span> <span class="token class-name">K</span> key<span class="token punctuation">,</span> <span class="token class-name">V</span> value<span class="token punctuation">,</span> <span class="token keyword">boolean</span> onlyIfAbsent<span class="token punctuation">,</span></pre></td></tr><tr><td data-num="6"></td><td><pre>                   <span class="token keyword">boolean</span> evict<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>    <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span><span class="token punctuation">[</span><span class="token punctuation">]</span> tab<span class="token punctuation">;</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span> p<span class="token punctuation">;</span> <span class="token keyword">int</span> n<span class="token punctuation">,</span> i<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>    <span class="token comment">// 判断数组是否未初始化</span></pre></td></tr><tr><td data-num="9"></td><td><pre>    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>tab <span class="token operator">=</span> table<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token keyword">null</span> <span class="token operator">||</span> <span class="token punctuation">(</span>n <span class="token operator">=</span> tab<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="10"></td><td><pre>        <span class="token comment">// 如果未初始化，调用 resize 方法 进行初始化</span></pre></td></tr><tr><td data-num="11"></td><td><pre>        n <span class="token operator">=</span> <span class="token punctuation">(</span>tab <span class="token operator">=</span> <span class="token function">resize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">.</span>length<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre>    <span class="token comment">// 通过 &amp; 运算求出该数据（key）的数组下标并判断该下标位置是否有数据</span></pre></td></tr><tr><td data-num="13"></td><td><pre>    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>p <span class="token operator">=</span> tab<span class="token punctuation">[</span>i <span class="token operator">=</span> <span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&amp;</span> hash<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="14"></td><td><pre>        <span class="token comment">// 如果没有，直接将数据放在该下标位置</span></pre></td></tr><tr><td data-num="15"></td><td><pre>        tab<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">newNode</span><span class="token punctuation">(</span>hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre>    <span class="token comment">// 该数组下标有数据的情况</span></pre></td></tr><tr><td data-num="17"></td><td><pre>    <span class="token keyword">else</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="18"></td><td><pre>        <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span> e<span class="token punctuation">;</span> <span class="token class-name">K</span> k<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre>        <span class="token comment">// 判断该位置数据的 key 和新来的数据是否一样</span></pre></td></tr><tr><td data-num="20"></td><td><pre>        <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token punctuation">.</span>hash <span class="token operator">==</span> hash <span class="token operator">&amp;&amp;</span></pre></td></tr><tr><td data-num="21"></td><td><pre>            <span class="token punctuation">(</span><span class="token punctuation">(</span>k <span class="token operator">=</span> p<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span> <span class="token punctuation">(</span>key <span class="token operator">!=</span> <span class="token keyword">null</span> <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="22"></td><td><pre>            <span class="token comment">// 如果一样，证明为修改操作，该节点的数据赋值给 e, 后边会用到</span></pre></td></tr><tr><td data-num="23"></td><td><pre>            e <span class="token operator">=</span> p<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre>        <span class="token comment">// 判断是不是红黑树</span></pre></td></tr><tr><td data-num="25"></td><td><pre>        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>p <span class="token keyword">instanceof</span> <span class="token class-name">TreeNode</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="26"></td><td><pre>            <span class="token comment">// 如果是红黑树的话，进行红黑树的操作</span></pre></td></tr><tr><td data-num="27"></td><td><pre>            e <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token class-name">TreeNode</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span><span class="token punctuation">)</span>p<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">putTreeVal</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">,</span> tab<span class="token punctuation">,</span> hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre>        <span class="token comment">// 新数据和当前数组既不相同，也不是红黑树节点，证明是链表</span></pre></td></tr><tr><td data-num="29"></td><td><pre>        <span class="token keyword">else</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="30"></td><td><pre>            <span class="token comment">// 遍历链表</span></pre></td></tr><tr><td data-num="31"></td><td><pre>            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> binCount <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">;</span> <span class="token operator">++</span>binCount<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="32"></td><td><pre>                <span class="token comment">// 判断 next 节点，如果为空的话，证明遍历到链表尾部了</span></pre></td></tr><tr><td data-num="33"></td><td><pre>                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e <span class="token operator">=</span> p<span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="34"></td><td><pre>                    <span class="token comment">// 把新值放入链表尾部</span></pre></td></tr><tr><td data-num="35"></td><td><pre>                    p<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">newNode</span><span class="token punctuation">(</span>hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="36"></td><td><pre>                    <span class="token comment">// 因为新插入了一条数据，所以判断链表长度是不是大于等于 8</span></pre></td></tr><tr><td data-num="37"></td><td><pre>                    <span class="token keyword">if</span> <span class="token punctuation">(</span>binCount <span class="token operator">>=</span> <span class="token constant">TREEIFY_THRESHOLD</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token comment">// -1 for 1st</span></pre></td></tr><tr><td data-num="38"></td><td><pre>                        <span class="token comment">// 如果是，进行转换红黑树操作</span></pre></td></tr><tr><td data-num="39"></td><td><pre>                        <span class="token function">treeifyBin</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> hash<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="40"></td><td><pre>                    <span class="token keyword">break</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="41"></td><td><pre>                <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="42"></td><td><pre>                <span class="token comment">// 判断链表当中有数据相同的值，如果一样，证明为修改操作</span></pre></td></tr><tr><td data-num="43"></td><td><pre>                <span class="token keyword">if</span> <span class="token punctuation">(</span>e<span class="token punctuation">.</span>hash <span class="token operator">==</span> hash <span class="token operator">&amp;&amp;</span></pre></td></tr><tr><td data-num="44"></td><td><pre>                    <span class="token punctuation">(</span><span class="token punctuation">(</span>k <span class="token operator">=</span> e<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span> <span class="token punctuation">(</span>key <span class="token operator">!=</span> <span class="token keyword">null</span> <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="45"></td><td><pre>                    <span class="token keyword">break</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="46"></td><td><pre>                <span class="token comment">// 把下一个节点赋值为当前节点</span></pre></td></tr><tr><td data-num="47"></td><td><pre>                p <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="48"></td><td><pre>            <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="49"></td><td><pre>        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="50"></td><td><pre>        <span class="token comment">// 判断 e 是否为空（e 值为修改操作存放原数据的变量）</span></pre></td></tr><tr><td data-num="51"></td><td><pre>        <span class="token keyword">if</span> <span class="token punctuation">(</span>e <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token comment">// existing mapping for key</span></pre></td></tr><tr><td data-num="52"></td><td><pre>            <span class="token comment">// 不为空的话证明是修改操作，取出老值</span></pre></td></tr><tr><td data-num="53"></td><td><pre>            <span class="token class-name">V</span> oldValue <span class="token operator">=</span> e<span class="token punctuation">.</span>value<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="54"></td><td><pre>            <span class="token comment">// 一定会执行  onlyIfAbsent 传进来的是 false</span></pre></td></tr><tr><td data-num="55"></td><td><pre>            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>onlyIfAbsent <span class="token operator">||</span> oldValue <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="56"></td><td><pre>                <span class="token comment">// 将新值赋值当前节点</span></pre></td></tr><tr><td data-num="57"></td><td><pre>                e<span class="token punctuation">.</span>value <span class="token operator">=</span> value<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="58"></td><td><pre>            <span class="token function">afterNodeAccess</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="59"></td><td><pre>            <span class="token comment">// 返回老值</span></pre></td></tr><tr><td data-num="60"></td><td><pre>            <span class="token keyword">return</span> oldValue<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="61"></td><td><pre>        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="62"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="63"></td><td><pre>    <span class="token comment">// 计数器，计算当前节点的修改次数</span></pre></td></tr><tr><td data-num="64"></td><td><pre>    <span class="token operator">++</span>modCount<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="65"></td><td><pre>    <span class="token comment">// 当前数组中的数据数量如果大于扩容阈值</span></pre></td></tr><tr><td data-num="66"></td><td><pre>    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">++</span>size <span class="token operator">></span> threshold<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="67"></td><td><pre>        <span class="token comment">// 进行扩容操作</span></pre></td></tr><tr><td data-num="68"></td><td><pre>        <span class="token function">resize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="69"></td><td><pre>    <span class="token comment">// 空方法</span></pre></td></tr><tr><td data-num="70"></td><td><pre>    <span class="token function">afterNodeInsertion</span><span class="token punctuation">(</span>evict<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="71"></td><td><pre>    <span class="token comment">// 添加操作时 返回空值</span></pre></td></tr><tr><td data-num="72"></td><td><pre>    <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="73"></td><td><pre><span class="token punctuation">&#125;</span></pre></td></tr></table></figure><ol><li><p>判断键值对数组 table 是否为空或为 null，否则执行 resize () 进行扩容（初始化）</p></li><li><p>根据键值 key 计算 hash 值得到数组索引</p></li><li><p>判断 table [i]==null，条件成立，直接新建节点添加</p></li><li><p>如果 table [i]==null , 不成立</p><p>4.1 判断 table [i] 的首个元素是否和 key 一样，如果相同直接覆盖 value</p><p>4.2 判断 table [i] 是否为 treeNode，即 table [i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对</p><p>4.3 遍历 table [i]，链表的尾部插入数据，然后判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操 作，遍历过程中若发现 key 已经存在直接覆盖 value</p></li><li><p>插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold（数组长度 * 0.75），如果超过，进行扩容。</p></li></ol><h3 id="35-面试题-讲一讲hashmap的扩容机制"><a class="anchor" href="#35-面试题-讲一讲hashmap的扩容机制">#</a> 3.5 面试题 - 讲一讲 HashMap 的扩容机制</h3><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428210844694.png" alt="image-20230428210844694"></p><p>扩容的流程：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428211031968.png" alt="image-20230428211031968"></p><p>源码：</p><figure class="highlight java"><figcaption data-lang="java"></figcaption><table><tr><td data-num="1"></td><td><pre><span class="token comment">// 扩容、初始化数组</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">final</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token function">resize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>        <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span><span class="token punctuation">[</span><span class="token punctuation">]</span> oldTab <span class="token operator">=</span> table<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>    	<span class="token comment">// 如果当前数组为 null 的时候，把 oldCap 老数组容量设置为 0</span></pre></td></tr><tr><td data-num="5"></td><td><pre>        <span class="token keyword">int</span> oldCap <span class="token operator">=</span> <span class="token punctuation">(</span>oldTab <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token number">0</span> <span class="token operator">:</span> oldTab<span class="token punctuation">.</span>length<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>        <span class="token comment">// 老的扩容阈值</span></pre></td></tr><tr><td data-num="7"></td><td><pre>    	<span class="token keyword">int</span> oldThr <span class="token operator">=</span> threshold<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>        <span class="token keyword">int</span> newCap<span class="token punctuation">,</span> newThr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>        <span class="token comment">// 判断数组容量是否大于 0，大于 0 说明数组已经初始化</span></pre></td></tr><tr><td data-num="10"></td><td><pre>    	<span class="token keyword">if</span> <span class="token punctuation">(</span>oldCap <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="11"></td><td><pre>            <span class="token comment">// 判断当前数组长度是否大于最大数组长度</span></pre></td></tr><tr><td data-num="12"></td><td><pre>            <span class="token keyword">if</span> <span class="token punctuation">(</span>oldCap <span class="token operator">>=</span> <span class="token constant">MAXIMUM_CAPACITY</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="13"></td><td><pre>                <span class="token comment">// 如果是，将扩容阈值直接设置为 int 类型的最大数值并直接返回</span></pre></td></tr><tr><td data-num="14"></td><td><pre>                threshold <span class="token operator">=</span> <span class="token class-name">Integer</span><span class="token punctuation">.</span><span class="token constant">MAX_VALUE</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre>                <span class="token keyword">return</span> oldTab<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre>            <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="17"></td><td><pre>            <span class="token comment">// 如果在最大长度范围内，则需要扩容  OldCap &lt;&lt; 1 等价于 oldCap*2</span></pre></td></tr><tr><td data-num="18"></td><td><pre>            <span class="token comment">// 运算过后判断是不是最大值并且 oldCap 需要大于 16</span></pre></td></tr><tr><td data-num="19"></td><td><pre>            <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>newCap <span class="token operator">=</span> oldCap <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token constant">MAXIMUM_CAPACITY</span> <span class="token operator">&amp;&amp;</span></pre></td></tr><tr><td data-num="20"></td><td><pre>                     oldCap <span class="token operator">>=</span> <span class="token constant">DEFAULT_INITIAL_CAPACITY</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="21"></td><td><pre>                newThr <span class="token operator">=</span> oldThr <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">//double threshold  等价于 oldThr*2</span></pre></td></tr><tr><td data-num="22"></td><td><pre>        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="23"></td><td><pre>    	<span class="token comment">// 如果 oldCap&lt;0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在，       			如果是首次初始化，它的临界值则为 0</span></pre></td></tr><tr><td data-num="24"></td><td><pre>        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>oldThr <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token comment">// initial capacity was placed in threshold</span></pre></td></tr><tr><td data-num="25"></td><td><pre>            newCap <span class="token operator">=</span> oldThr<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="26"></td><td><pre>        <span class="token comment">// 数组未初始化的情况，将阈值和扩容因子都设置为默认值</span></pre></td></tr><tr><td data-num="27"></td><td><pre>    	<span class="token keyword">else</span> <span class="token punctuation">&#123;</span>               <span class="token comment">// zero initial threshold signifies using defaults</span></pre></td></tr><tr><td data-num="28"></td><td><pre>            newCap <span class="token operator">=</span> <span class="token constant">DEFAULT_INITIAL_CAPACITY</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="29"></td><td><pre>            newThr <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token constant">DEFAULT_LOAD_FACTOR</span> <span class="token operator">*</span> <span class="token constant">DEFAULT_INITIAL_CAPACITY</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="30"></td><td><pre>        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="31"></td><td><pre>    	<span class="token comment">// 初始化容量小于 16 的时候，扩容阈值是没有赋值的</span></pre></td></tr><tr><td data-num="32"></td><td><pre>        <span class="token keyword">if</span> <span class="token punctuation">(</span>newThr <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="33"></td><td><pre>            <span class="token comment">// 创建阈值</span></pre></td></tr><tr><td data-num="34"></td><td><pre>            <span class="token keyword">float</span> ft <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">float</span><span class="token punctuation">)</span>newCap <span class="token operator">*</span> loadFactor<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="35"></td><td><pre>            <span class="token comment">// 判断新容量和新阈值是否大于最大容量</span></pre></td></tr><tr><td data-num="36"></td><td><pre>            newThr <span class="token operator">=</span> <span class="token punctuation">(</span>newCap <span class="token operator">&lt;</span> <span class="token constant">MAXIMUM_CAPACITY</span> <span class="token operator">&amp;&amp;</span> ft <span class="token operator">&lt;</span> <span class="token punctuation">(</span><span class="token keyword">float</span><span class="token punctuation">)</span><span class="token constant">MAXIMUM_CAPACITY</span> <span class="token operator">?</span></pre></td></tr><tr><td data-num="37"></td><td><pre>                      <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span>ft <span class="token operator">:</span> <span class="token class-name">Integer</span><span class="token punctuation">.</span><span class="token constant">MAX_VALUE</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="38"></td><td><pre>        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="39"></td><td><pre>    	<span class="token comment">// 计算出来的阈值赋值</span></pre></td></tr><tr><td data-num="40"></td><td><pre>        threshold <span class="token operator">=</span> newThr<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="41"></td><td><pre>        <span class="token annotation punctuation">@SuppressWarnings</span><span class="token punctuation">(</span><span class="token punctuation">&#123;</span><span class="token string">"rawtypes"</span><span class="token punctuation">,</span><span class="token string">"unchecked"</span><span class="token punctuation">&#125;</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="42"></td><td><pre>        <span class="token comment">// 根据上边计算得出的容量 创建新的数组       </span></pre></td></tr><tr><td data-num="43"></td><td><pre>    	<span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span><span class="token punctuation">[</span><span class="token punctuation">]</span> newTab <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">[</span>newCap<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="44"></td><td><pre>    	<span class="token comment">// 赋值</span></pre></td></tr><tr><td data-num="45"></td><td><pre>    	table <span class="token operator">=</span> newTab<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="46"></td><td><pre>    	<span class="token comment">// 扩容操作，判断不为空证明不是初始化数组</span></pre></td></tr><tr><td data-num="47"></td><td><pre>        <span class="token keyword">if</span> <span class="token punctuation">(</span>oldTab <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="48"></td><td><pre>            <span class="token comment">// 遍历数组</span></pre></td></tr><tr><td data-num="49"></td><td><pre>            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> oldCap<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="50"></td><td><pre>                <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="51"></td><td><pre>                <span class="token comment">// 判断当前下标为 j 的数组如果不为空的话赋值个 e，进行下一步操作</span></pre></td></tr><tr><td data-num="52"></td><td><pre>                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e <span class="token operator">=</span> oldTab<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="53"></td><td><pre>                    <span class="token comment">// 将数组位置置空</span></pre></td></tr><tr><td data-num="54"></td><td><pre>                    oldTab<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="55"></td><td><pre>                    <span class="token comment">// 判断是否有下个节点</span></pre></td></tr><tr><td data-num="56"></td><td><pre>                    <span class="token keyword">if</span> <span class="token punctuation">(</span>e<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="57"></td><td><pre>                        <span class="token comment">// 如果没有，就重新计算在新数组中的下标并放进去</span></pre></td></tr><tr><td data-num="58"></td><td><pre>                        newTab<span class="token punctuation">[</span>e<span class="token punctuation">.</span>hash <span class="token operator">&amp;</span> <span class="token punctuation">(</span>newCap <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="59"></td><td><pre>                   	<span class="token comment">// 有下个节点的情况，并且判断是否已经树化</span></pre></td></tr><tr><td data-num="60"></td><td><pre>                    <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>e <span class="token keyword">instanceof</span> <span class="token class-name">TreeNode</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="61"></td><td><pre>                        <span class="token comment">// 进行红黑树的操作</span></pre></td></tr><tr><td data-num="62"></td><td><pre>                        <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token class-name">TreeNode</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span><span class="token punctuation">)</span>e<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">split</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">,</span> newTab<span class="token punctuation">,</span> j<span class="token punctuation">,</span> oldCap<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="63"></td><td><pre>                    <span class="token comment">// 有下个节点的情况，并且没有树化（链表形式）</span></pre></td></tr><tr><td data-num="64"></td><td><pre>                    <span class="token keyword">else</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="65"></td><td><pre>                        <span class="token comment">// 比如老数组容量是 16，那下标就为 0-15</span></pre></td></tr><tr><td data-num="66"></td><td><pre>                        <span class="token comment">// 扩容操作 * 2，容量就变为 32，下标为 0-31</span></pre></td></tr><tr><td data-num="67"></td><td><pre>                        <span class="token comment">// 低位：0-15，高位 16-31</span></pre></td></tr><tr><td data-num="68"></td><td><pre>                        <span class="token comment">// 定义了四个变量</span></pre></td></tr><tr><td data-num="69"></td><td><pre>                        <span class="token comment">//        低位头          低位尾</span></pre></td></tr><tr><td data-num="70"></td><td><pre>                        <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span> loHead <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">,</span> loTail <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="71"></td><td><pre>                        <span class="token comment">//        高位头		   高位尾</span></pre></td></tr><tr><td data-num="72"></td><td><pre>                        <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span> hiHead <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">,</span> hiTail <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="73"></td><td><pre>                        <span class="token comment">// 下个节点</span></pre></td></tr><tr><td data-num="74"></td><td><pre>                        <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">></span></span> next<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="75"></td><td><pre>                        <span class="token comment">// 循环遍历</span></pre></td></tr><tr><td data-num="76"></td><td><pre>                        <span class="token keyword">do</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="77"></td><td><pre>                            <span class="token comment">// 取出 next 节点</span></pre></td></tr><tr><td data-num="78"></td><td><pre>                            next <span class="token operator">=</span> e<span class="token punctuation">.</span>next<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="79"></td><td><pre>                            <span class="token comment">// 通过 与操作 计算得出结果为 0</span></pre></td></tr><tr><td data-num="80"></td><td><pre>                            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e<span class="token punctuation">.</span>hash <span class="token operator">&amp;</span> oldCap<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="81"></td><td><pre>                                <span class="token comment">// 如果低位尾为 null，证明当前数组位置为空，没有任何数据</span></pre></td></tr><tr><td data-num="82"></td><td><pre>                                <span class="token keyword">if</span> <span class="token punctuation">(</span>loTail <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="83"></td><td><pre>                                    <span class="token comment">// 将 e 值放入低位头</span></pre></td></tr><tr><td data-num="84"></td><td><pre>                                    loHead <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="85"></td><td><pre>                                <span class="token comment">// 低位尾不为 null，证明已经有数据了</span></pre></td></tr><tr><td data-num="86"></td><td><pre>                                <span class="token keyword">else</span></pre></td></tr><tr><td data-num="87"></td><td><pre>                                    <span class="token comment">// 将数据放入 next 节点</span></pre></td></tr><tr><td data-num="88"></td><td><pre>                                    loTail<span class="token punctuation">.</span>next <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="89"></td><td><pre>                                <span class="token comment">// 记录低位尾数据</span></pre></td></tr><tr><td data-num="90"></td><td><pre>                                loTail <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="91"></td><td><pre>                            <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="92"></td><td><pre>                            <span class="token comment">// 通过 与操作 计算得出结果不为 0</span></pre></td></tr><tr><td data-num="93"></td><td><pre>                            <span class="token keyword">else</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="94"></td><td><pre>                                 <span class="token comment">// 如果高位尾为 null，证明当前数组位置为空，没有任何数据</span></pre></td></tr><tr><td data-num="95"></td><td><pre>                                <span class="token keyword">if</span> <span class="token punctuation">(</span>hiTail <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="96"></td><td><pre>                                    <span class="token comment">// 将 e 值放入高位头</span></pre></td></tr><tr><td data-num="97"></td><td><pre>                                    hiHead <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="98"></td><td><pre>                                <span class="token comment">// 高位尾不为 null，证明已经有数据了</span></pre></td></tr><tr><td data-num="99"></td><td><pre>                                <span class="token keyword">else</span></pre></td></tr><tr><td data-num="100"></td><td><pre>                                    <span class="token comment">// 将数据放入 next 节点</span></pre></td></tr><tr><td data-num="101"></td><td><pre>                                    hiTail<span class="token punctuation">.</span>next <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="102"></td><td><pre>                               <span class="token comment">// 记录高位尾数据</span></pre></td></tr><tr><td data-num="103"></td><td><pre>                               	hiTail <span class="token operator">=</span> e<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="104"></td><td><pre>                            <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="105"></td><td><pre>                            </pre></td></tr><tr><td data-num="106"></td><td><pre>                        <span class="token punctuation">&#125;</span> </pre></td></tr><tr><td data-num="107"></td><td><pre>                        <span class="token comment">// 如果 e 不为空，证明没有到链表尾部，继续执行循环</span></pre></td></tr><tr><td data-num="108"></td><td><pre>                        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e <span class="token operator">=</span> next<span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="109"></td><td><pre>                        <span class="token comment">// 低位尾如果记录的有数据，是链表</span></pre></td></tr><tr><td data-num="110"></td><td><pre>                        <span class="token keyword">if</span> <span class="token punctuation">(</span>loTail <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="111"></td><td><pre>                            <span class="token comment">// 将下一个元素置空</span></pre></td></tr><tr><td data-num="112"></td><td><pre>                            loTail<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="113"></td><td><pre>                            <span class="token comment">// 将低位头放入新数组的原下标位置</span></pre></td></tr><tr><td data-num="114"></td><td><pre>                            newTab<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> loHead<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="115"></td><td><pre>                        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="116"></td><td><pre>                        <span class="token comment">// 高位尾如果记录的有数据，是链表</span></pre></td></tr><tr><td data-num="117"></td><td><pre>                        <span class="token keyword">if</span> <span class="token punctuation">(</span>hiTail <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span></pre></td></tr><tr><td data-num="118"></td><td><pre>                            <span class="token comment">// 将下一个元素置空</span></pre></td></tr><tr><td data-num="119"></td><td><pre>                            hiTail<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="120"></td><td><pre>                            <span class="token comment">// 将高位头放入新数组的 (原下标 + 原数组容量) 位置</span></pre></td></tr><tr><td data-num="121"></td><td><pre>                            newTab<span class="token punctuation">[</span>j <span class="token operator">+</span> oldCap<span class="token punctuation">]</span> <span class="token operator">=</span> hiHead<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="122"></td><td><pre>                        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="123"></td><td><pre>                    <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="124"></td><td><pre>                <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="125"></td><td><pre>            <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="126"></td><td><pre>        <span class="token punctuation">&#125;</span></pre></td></tr><tr><td data-num="127"></td><td><pre>    	<span class="token comment">// 返回新的数组对象</span></pre></td></tr><tr><td data-num="128"></td><td><pre>        <span class="token keyword">return</span> newTab<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="129"></td><td><pre>    <span class="token punctuation">&#125;</span></pre></td></tr></table></figure><ul><li><p>在添加元素或初始化的时候需要调用 resize 方法进行扩容，第一次添加数据初始化数组长度为 16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）</p></li><li><p>每次扩容的时候，都是扩容之前容量的 2 倍；</p></li><li><p>扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中</p><ul><li>没有 hash 冲突的节点，则直接使用 e.hash &amp; (newCap - 1) 计算新数组的索引位置</li><li>如果是红黑树，走红黑树的添加</li><li>如果是链表，则需要遍历链表，可能需要拆分链表，判断 (e.hash &amp; oldCap) 是否为 0，该元素的位置要么停留在原始位置，要么移动到原始位置 + 增加的数组大小这个位置上</li></ul></li></ul><h3 id="36-面试题-hashmap的寻址算法"><a class="anchor" href="#36-面试题-hashmap的寻址算法">#</a> 3.6 面试题 - hashMap 的寻址算法</h3><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428212501408.png" alt="image-20230428212501408"></p><p>在 putVal 方法中，有一个 hash (key) 方法，这个方法就是来去计算 key 的 hash 值的，看下面的代码</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428212601977.png" alt="image-20230428212601977"></p><p>首先获取 key 的 hashCode 值，然后右移 16 位 异或运算 原来的 hashCode 值，主要作用就是使原来的 hash 值更加均匀，减少 hash 冲突</p><p>有了 hash 值之后，就很方便的去计算当前 key 的在数组中存储的下标，看下面的代码：</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428212729580.png" alt="image-20230428212729580"></p><p>(n-1)&amp;hash : 得到数组中的索引，代替取模，性能更好，数组长度必须是 2 的 n 次幂</p><p><strong>关于 hash 值的其他面试题：为何 HashMap 的数组长度一定是 2 的次幂？</strong></p><ol><li><p>计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模</p></li><li><p>扩容时重新计算索引效率更高： hash &amp; oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap</p></li></ol><h3 id="37-面试题-hashmap在17情况下的多线程死循环问题"><a class="anchor" href="#37-面试题-hashmap在17情况下的多线程死循环问题">#</a> 3.7 面试题 - hashmap 在 1.7 情况下的多线程死循环问题</h3><p>jdk7 的的数据结构是：数组 + 链表</p><p>在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428213115071.png" alt="image-20230428213115071"></p><ul><li><p>变量 e 指向的是需要迁移的对象</p></li><li><p>变量 next 指向的是下一个需要迁移的对象</p></li><li><p>Jdk1.7 中的链表采用的头插法</p></li><li><p>在数据迁移的过程中并没有新的对象产生，只是改变了对象的引用</p></li></ul><p>产生死循环的过程：</p><p>线程 1 和线程 2 的变量 e 和 next 都引用了这个两个节点</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428213533483.png" alt="image-20230428213533483"></p><p>线程 2 扩容后，由于头插法，链表顺序颠倒，但是线程 1 的临时变量 e 和 next 还引用了这两个节点</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428214732877.png" alt="image-20230428214732877"></p><p>第一次循环</p><p>由于线程 2 迁移的时候，已经把 B 的 next 执行了 A</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428214806072.png" alt="image-20230428214806072"></p><p>第二次循环</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428214908652.png" alt="image-20230428214908652"></p><p>第三次循环</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20230428214937231.png" alt="image-20230428214937231"></p><p>参考回答：</p><p>在 jdk1.7 的 hashmap 中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环</p><p>比如说，现在有两个线程</p><p>线程一：读取到当前的 hashmap 数据，数据中一个链表，在准备扩容时，线程二介入</p><p>线程二：也读取 hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是 AB，扩容后的顺序是 BA，线程二执行结束。</p><p>线程一：继续执行的时候就会出现死循环的问题。</p><p>线程一先将 A 移入新的链表，再将 B 插入到链头，由于另外一个线程的原因，B 的 next 指向了 A，</p><p>所以 B-&gt;A-&gt;B, 形成循环。</p><p>当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），<strong>尾插法</strong>，就避免了 jdk7 中死循环的问题。</p><h3 id="38-面试题-hashset与hashmap的区别"><a class="anchor" href="#38-面试题-hashset与hashmap的区别">#</a> 3.8 面试题 - HashSet 与 HashMap 的区别</h3><p>(1) HashSet 实现了 Set 接口，仅存储对象；HashMap 实现了 Map 接口，存储的是键值对.</p><p>(2) HashSet 底层其实是用 HashMap 实现存储的，HashSet 封装了一系列 HashMap 的方法。依靠 HashMap 来存储元素值，(利用 hashMap 的 key 键进行存储), 而 value 值默认为 Object 对象。所以 HashSet 也不允许出现重复值，判断标准和 HashMap 判断标准相同，两个元素的 hashCode 相等并且通过 equals () 方法返回 true.</p><p><img data-src="https://anoxia-picgo.oss-cn-beijing.aliyuncs.com/image-20221007110404375.png" alt="image-20221007110404375"></p><h3 id="39-面试题-hashtable与hashmap的区别"><a class="anchor" href="#39-面试题-hashtable与hashmap的区别">#</a> 3.9 面试题 - HashTable 与 HashMap 的区别</h3><blockquote><p>难易程度：☆☆</p><p>出现频率：☆☆</p></blockquote><p>主要区别：</p><table><thead><tr><th><strong>区别</strong></th><th><strong>HashTable</strong></th><th><strong>HashMap</strong></th></tr></thead><tbody><tr><td>数据结构</td><td>数组 + 链表</td><td>数组 + 链表 + 红黑树</td></tr><tr><td>是否可以为 null</td><td>Key 和 value 都不能为 null</td><td>可以为 null</td></tr><tr><td>hash 算法</td><td>key 的 hashCode ()</td><td>二次 hash</td></tr><tr><td>扩容方式</td><td>当前容量翻倍 +1</td><td>当前容量翻倍</td></tr><tr><td>线程安全</td><td>同步 (synchronized) 的，线程安全</td><td>非线程安全</td></tr></tbody></table><p>在实际开中不建议使用 HashTable，在多线程环境下可以使用 ConcurrentHashMap 类</p><h2 id="3-真实面试还原"><a class="anchor" href="#3-真实面试还原">#</a> 3 真实面试还原</h2><h3 id="31-java常见的集合类"><a class="anchor" href="#31-java常见的集合类">#</a> 3.1 Java 常见的集合类</h3><blockquote><p><strong>面试官</strong>：说一说 Java 提供的常见集合？（画一下集合结构图）</p><p><strong>候选人</strong>：</p><p>嗯～～，好的。</p><p>在 java 中提供了量大类的集合框架，主要分为两类：</p><p>第一个是 Collection 属于单列集合，第二个是 Map 属于双列集合</p><ul><li>在 Collection 中有两个子接口 List 和 Set。在我们平常开发的过程中用的比较多像 list 接口中的实现类 ArrarList 和 LinkedList。 在 Set 接口中有实现类 HashSet 和 TreeSet。</li><li>在 map 接口中有很多的实现类，平时比较常见的是 HashMap、TreeMap，还有一个线程安全的 map:ConcurrentHashMap</li></ul></blockquote><h3 id="32-list"><a class="anchor" href="#32-list">#</a> 3.2 List</h3><blockquote><p><strong>面试官</strong>：ArrayList 底层是如何实现的？</p><p><strong>候选人</strong>：</p><p>嗯～，我阅读过 arraylist 的源码，我主要说一下 add 方法吧</p><p>第一：确保数组已使用长度（size）加 1 之后足够存下下一个数据</p><p>第二：计算数组的容量，如果当前数组已使用长度 + 1 后的大于当前的数组长度，则调用 grow 方法扩容（原来的 1.5 倍）</p><p>第三：确保新增的数据有地方存储之后，则将新元素添加到位于 size 的位置上。</p><p>第四：返回添加成功布尔值。</p><p><strong>面试官</strong>：ArrayList list=new ArrayList (10) 中的 list 扩容几次</p><p><strong>候选人</strong>：</p><p>​	是 new 了一个 ArrarList 并且给了一个构造参数 10，对吧？(问题一定要问清楚再答)</p><p><strong>面试官</strong>：是的</p><p><strong>候选人</strong>：</p><p>​ 好的，在 ArrayList 的源码中提供了一个带参数的构造方法，这个参数就是指定的集合初始长度，所以给了一个 10 的参数，就是指定了集合的初始长度是 10，这里面并没有扩容。</p><hr><p><strong>面试官</strong>：如何实现数组和 List 之间的转换</p><p><strong>候选人</strong>：</p><p>​	嗯，这个在我们平时开发很常见</p><p>​ 数组转 list，可以使用 jdk 自动的一个工具类 Arrars，里面有一个 asList 方法可以转换为数组</p><p>​ List 转数组，可以直接调用 list 中的 toArray 方法，需要给一个参数，指定数组的类型，需要指定数组的长度。</p><p><strong>面试官</strong>：用 Arrays.asList 转 List 后，如果修改了数组内容，list 受影响吗？List 用 toArray 转数组后，如果修改了 List 内容，数组受影响吗</p><p><strong>候选人</strong>：</p><p>Arrays.asList 转换 list 之后，如果修改了数组的内容，list 会受影响，因为它的底层使用的 Arrays 类中的一个内部类 ArrayList 来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址</p><p>list 用了 toArray 转数组后，如果修改了 list 内容，数组不会影响，当调用了 toArray 以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使 list 修改了以后，数组也不受影响</p><hr><p><strong>面试官</strong>：ArrayList 和 LinkedList 的区别是什么？</p><p><strong>候选人</strong>：</p><p>嗯，它们两个主要是底层使用的数据结构不一样，ArrayList 是动态数组，LinkedList 是双向链表，这也导致了它们很多不同的特点。</p><p>1，从操作数据效率来说</p><p>ArrayList 按照下标查询的时间复杂度 O (1)【内存是连续的，根据寻址公式】， LinkedList 不支持下标查询</p><p>查找（未知索引）： ArrayList 需要遍历，链表也需要链表，时间复杂度都是 O (n)</p><p>新增和删除</p><ul><li>ArrayList 尾部插入和删除，时间复杂度是 O (1)；其他部分增删需要挪动数组，时间复杂度是 O (n)</li><li>LinkedList 头尾节点增删时间复杂度是 O (1)，其他都需要遍历链表，时间复杂度是 O (n)</li></ul><p>2，从内存空间占用来说</p><p>ArrayList 底层是数组，内存连续，节省内存</p><p>LinkedList 是双向链表需要存储数据，和两个指针，更占用内存</p><p>3，从线程安全来说，ArrayList 和 LinkedList 都不是线程安全的</p><p><strong>面试官</strong>：嗯，好的，刚才你说了 ArrayList 和 LinkedList 不是线程安全的，你们在项目中是如何解决这个的线程安全问题的？</p><p><strong>候选人</strong>：</p><p>嗯，是这样的，主要有两种解决方案：</p><p>第一：我们使用这个集合，优先在方法内使用，定义为局部变量，这样的话，就不会出现线程安全问题。</p><p>第二：如果非要在成员变量中使用的话，可以使用线程安全的集合来替代</p><p>ArrayList 可以通过 Collections 的 synchronizedList 方法将 ArrayList 转换成线程安全的容器后再使用。</p><p>LinkedList 换成 ConcurrentLinkedQueue 来使用</p></blockquote><h3 id="34-hashmap"><a class="anchor" href="#34-hashmap">#</a> 3.4 HashMap</h3><blockquote><p><strong>面试官</strong>：说一下 HashMap 的实现原理？</p><p><strong>候选人</strong>：</p><p>​	嗯。它主要分为了一下几个部分：</p><p>1，底层使用 hash 表数据结构，即数组 +（链表 | 红黑树）</p><p>2，添加数据时，计算 key 的值确定元素在数组中的下标</p><p>​	key 相同则替换</p><p>​	不同则存入链表或红黑树中</p><p>3，获取数据通过 key 的 hash 计算数组下标获取元素</p><p><strong>面试官</strong>：HashMap 的 jdk1.7 和 jdk1.8 有什么区别</p><p><strong>候选人</strong>：</p><ul><li><p>JDK1.8 之前采用的拉链法，数组 + 链表</p></li><li><p>JDK1.8 之后采用数组 + 链表 + 红黑树，链表长度大于 8 且数组长度大于 64 则会从链表转化为红黑树</p></li></ul><p><strong>面试官</strong>：好的，你能说下 HashMap 的 put 方法的具体流程吗？</p><p><strong>候选人</strong>：</p><p>嗯好的。</p><ol><li><p>判断键值对数组 table 是否为空或为 null，否则执行 resize () 进行扩容（初始化）</p></li><li><p>根据键值 key 计算 hash 值得到数组索引</p></li><li><p>判断 table [i]==null，条件成立，直接新建节点添加</p></li><li><p>如果 table [i]==null , 不成立</p></li></ol><p>4.1 判断 table [i] 的首个元素是否和 key 一样，如果相同直接覆盖 value</p><p>4.2 判断 table [i] 是否为 treeNode，即 table [i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对</p><p>4.3 遍历 table [i]，链表的尾部插入数据，然后判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操 作，遍历过程中若发现 key 已经存在直接覆盖 value</p><ol start="5"><li>插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold（数组长度 * 0.75），如果超过，进行扩容。</li></ol><p><strong>面试官</strong>：好的，刚才你多次介绍了 hsahmap 的扩容，能讲一讲 HashMap 的扩容机制吗？</p><p><strong>候选人</strong>：</p><p>好的</p><ul><li><p>在添加元素或初始化的时候需要调用 resize 方法进行扩容，第一次添加数据初始化数组长度为 16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）</p></li><li><p>每次扩容的时候，都是扩容之前容量的 2 倍；</p></li><li><p>扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中</p></li><li><p>没有 hash 冲突的节点，则直接使用 e.hash &amp; (newCap - 1) 计算新数组的索引位置</p></li><li><p>如果是红黑树，走红黑树的添加</p></li><li><p>如果是链表，则需要遍历链表，可能需要拆分链表，判断 (e.hash &amp; oldCap) 是否为 0，该元素的位置要么停留在原始位置，要么移动到原始位置 + 增加的数组大小这个位置上</p></li></ul><p><strong>面试官</strong>：好的，刚才你说的通过 hash 计算后找到数组的下标，是如何找到的呢，你了解 hashMap 的寻址算法吗？</p><p><strong>候选人</strong>：</p><p>这个哈希方法首先计算出 key 的 hashCode 值，然后通过这个 hash 值右移 16 位后的二进制进行按位<strong>异或运算</strong>得到最后的 hash 值。</p><p>在 putValue 的方法中，计算数组下标的时候使用 hash 值与数组长度取模得到存储数据下标的位置，hashmap 为了性能更好，并没有直接采用取模的方式，而是使用了数组长度 - 1 得到一个值，用这个值按位与运算 hash 值，最终得到数组的位置。</p><p><strong>面试官</strong>：为何 HashMap 的数组长度一定是 2 的次幂？</p><p><strong>候选人</strong>：</p><p>嗯，好的。hashmap 这么设计主要有两个原因：</p><p>第一：</p><p>计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模</p><p>第二：</p><p>扩容时重新计算索引效率更高：在进行扩容是会进行判断 hash 值按位与运算旧数组长租是否 == 0</p><p>如果等于 0，则把元素留在原来位置 ，否则新位置是等于旧位置的下标 + 旧数组长度</p><p><strong>面试官</strong>：好的，我看你对 hashmap 了解的挺深入的，你知道 hashmap 在 1.7 情况下的多线程死循环问题吗？</p><p><strong>候选人</strong>：</p><p>嗯，知道的。是这样</p><p>jdk7 的的数据结构是：数组 + 链表</p><p>在数组进行扩容的时候，因为链表是<strong>头插法</strong>，在进行数据迁移的过程中，有可能导致死循环</p><p>比如说，现在有两个线程</p><p>线程一：<strong>读取</strong>到当前的 hashmap 数据，数据中一个链表，在准备扩容时，线程二介入</p><p>线程二也读取 hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是 AB，扩容后的顺序是 BA，线程二执行结束。</p><p>当线程一再继续执行的时候就会出现死循环的问题。</p><p>线程一先将 A 移入新的链表，再将 B 插入到链头，由于另外一个线程的原因，B 的 next 指向了 A，所以 B-&gt;A-&gt;B, 形成循环。</p><p>当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），<strong>尾插法</strong>，就避免了 jdk7 中死循环的问题。</p><p><strong>面试官</strong>：好的，hashmap 是线程安全的吗？</p><p><strong>候选人</strong>：不是线程安全的</p><p><strong>面试官</strong>：那我们想要使用线程安全的 map 该怎么做呢？</p><p><strong>候选人</strong>：我们可以采用 ConcurrentHashMap 进行使用，它是一个线程安全的 HashMap</p><p><strong>面试官</strong>：那你能聊一下 ConcurrentHashMap 的原理吗？</p><p><strong>候选人</strong>：好的，请参考《多线程相关面试题》中的 ConcurrentHashMap 部分的讲解</p><hr><p><strong>面试官</strong>：HashSet 与 HashMap 的区别？</p><p><strong>候选人</strong>：嗯，是这样。</p><p>HashSet 底层其实是用 HashMap 实现存储的，HashSet 封装了一系列 HashMap 的方法。依靠 HashMap 来存储元素值，(利用 hashMap 的 key 键进行存储), 而 value 值默认为 Object 对象。所以 HashSet 也不允许出现重复值，判断标准和 HashMap 判断标准相同，两个元素的 hashCode 相等并且通过 equals () 方法返回 true.</p><p><strong>面试官</strong>：HashTable 与 HashMap 的区别</p><p><strong>候选人</strong>：</p><p>嗯，他们的主要区别是有几个吧</p><p>第一，数据结构不一样，hashtable 是数组 + 链表，hashmap 在 1.8 之后改为了数组 + 链表 + 红黑树</p><p>第二，hashtable 存储数据的时候都不能为 null，而 hashmap 是可以的</p><p>第三，hash 算法不同，hashtable 是用本地修饰的 hashcode 值，而 hashmap 经常了二次 hash</p><p>第四，扩容方式不同，hashtable 是当前容量翻倍 + 1，hashmap 是当前容量翻倍</p><p>第五，hashtable 是线程安全的，操作数据的时候加了锁 synchronized，hashmap 不是线程安全的，效率更高一些</p><p>在实际开中不建议使用 HashTable，在多线程环境下可以使用 ConcurrentHashMap 类</p></blockquote><div class="tags"><a href="/tags/Java%E5%9F%BA%E7%A1%80/" rel="tag"><i class="ic i-tag"></i> Java基础</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i> </span><span class="text">更新于</span> <time title="修改时间：2023-08-13 21:00:18" itemprop="dateModified" datetime="2023-08-13T21:00:18+08:00">2023-08-13</time> </span><span id="interview/Java集合相关面试题/" class="item leancloud_visitors" data-flag-title="Java集合相关面试题" title="阅读次数"><span class="icon"><i class="ic i-eye"></i> </span><span class="text">阅读次数</span> <span class="leancloud-visitors-count"></span> <span class="text">次</span></span></div><div class="reward"><button><i class="ic i-heartbeat"></i> 赞赏</button><p>请我喝[茶]~(￣▽￣)~*</p><div id="qr"><div><img data-src="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/images/weipay.png" alt="anoxia 微信支付"><p>微信支付</p></div><div><img data-src="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/images/alipay.png" alt="anoxia 支付宝"><p>支付宝</p></div></div></div><div id="copyright"><ul><li class="author"><strong>本文作者： </strong>anoxia <i class="ic i-at"><em>@</em></i></li><li class="link"><strong>本文链接：</strong> <a href="http://zero-yuan.gitee.io/interview/Java%E9%9B%86%E5%90%88%E7%9B%B8%E5%85%B3%E9%9D%A2%E8%AF%95%E9%A2%98/" title="Java集合相关面试题">http://zero-yuan.gitee.io/interview/Java集合相关面试题/</a></li><li class="license"><strong>版权声明： </strong>本站所有文章除特别声明外，均采用 <span class="exturl" data-url="aHR0cHM6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LW5jLXNhLzQuMC9kZWVkLnpo"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</span> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/interview/%E6%B6%88%E6%81%AF%E4%B8%AD%E9%97%B4%E4%BB%B6%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" itemprop="url" rel="prev" data-background-image="https:&#x2F;&#x2F;tse2-mm.cn.bing.net&#x2F;th&#x2F;id&#x2F;OIP-C.A_E5Ucxpc_-_N241EmD9_wHaEK?w&#x3D;259&amp;h&#x3D;180&amp;c&#x3D;7&amp;r&#x3D;0&amp;o&#x3D;5&amp;dpr&#x3D;1.3&amp;pid&#x3D;1.7" title="消息中间件相关面试题"><span class="type">上一篇</span> <span class="category"><i class="ic i-flag"></i> 面经</span><h3>消息中间件相关面试题</h3></a></div><div class="item right"></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-number">1.</span> <span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">2.</span> <span class="toc-text">1 算法复杂度分析</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#11-%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E8%BF%9B%E8%A1%8C%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">2.1.</span> <span class="toc-text">1.1 为什么要进行复杂度分析？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#12-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.2.</span> <span class="toc-text">1.2 时间复杂度</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#121-%E6%A1%88%E4%BE%8B"><span class="toc-number">2.2.1.</span> <span class="toc-text">1.2.1 案例</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#122-%E5%A4%A7o%E8%A1%A8%E7%A4%BA%E6%B3%95"><span class="toc-number">2.2.2.</span> <span class="toc-text">1.2.2 大 O 表示法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#123-%E5%B8%B8%E8%A7%81%E5%A4%8D%E6%9D%82%E5%BA%A6%E8%A1%A8%E7%A4%BA%E5%BD%A2%E5%BC%8F"><span class="toc-number">2.2.3.</span> <span class="toc-text">1.2.3 常见复杂度表示形式</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#124-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6o1"><span class="toc-number">2.2.4.</span> <span class="toc-text">1.2.4 时间复杂度 O (1)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#125-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6on"><span class="toc-number">2.2.5.</span> <span class="toc-text">1.2.5 时间复杂度 O (n)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#126-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6ologn"><span class="toc-number">2.2.6.</span> <span class="toc-text">1.2.6 时间复杂度 O (logn)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#127-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6on-log-n"><span class="toc-number">2.2.7.</span> <span class="toc-text">1.2.7 时间复杂度 O (n * log n)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#13-%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.3.</span> <span class="toc-text">1.3 空间复杂度</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-list%E7%9B%B8%E5%85%B3%E9%9D%A2%E8%AF%95%E9%A2%98"><span class="toc-number">3.</span> <span class="toc-text">2 List 相关面试题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#21-%E6%95%B0%E7%BB%84"><span class="toc-number">3.1.</span> <span class="toc-text">2.1 数组</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#211-%E6%95%B0%E7%BB%84%E6%A6%82%E8%BF%B0"><span class="toc-number">3.1.1.</span> <span class="toc-text">2.1.1 数组概述</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#212-%E5%AF%BB%E5%9D%80%E5%85%AC%E5%BC%8F"><span class="toc-number">3.1.2.</span> <span class="toc-text">2.1.2 寻址公式</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#213-%E6%93%8D%E4%BD%9C%E6%95%B0%E7%BB%84%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">3.1.3.</span> <span class="toc-text">2.1.3 操作数组的时间复杂度</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#22-arraylist%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90"><span class="toc-number">3.2.</span> <span class="toc-text">2.2 ArrayList 源码分析</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#221-%E6%88%90%E5%91%98%E5%8F%98%E9%87%8F"><span class="toc-number">3.2.1.</span> <span class="toc-text">2.2.1 成员变量</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#222-%E6%9E%84%E9%80%A0%E6%96%B9%E6%B3%95"><span class="toc-number">3.2.2.</span> <span class="toc-text">2.2.2 构造方法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#223-arraylist%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90"><span class="toc-number">3.2.3.</span> <span class="toc-text">2.2.3 ArrayList 源码分析</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#224-%E9%9D%A2%E8%AF%95%E9%A2%98-arraylist-listnew-arraylist10%E4%B8%AD%E7%9A%84list%E6%89%A9%E5%AE%B9%E5%87%A0%E6%AC%A1"><span class="toc-number">3.2.4.</span> <span class="toc-text">2.2.4 面试题 - ArrayList list&#x3D;new ArrayList (10) 中的 list 扩容几次</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#224-%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%A6%82%E4%BD%95%E5%AE%9E%E7%8E%B0%E6%95%B0%E7%BB%84%E5%92%8Clist%E4%B9%8B%E9%97%B4%E7%9A%84%E8%BD%AC%E6%8D%A2"><span class="toc-number">3.2.5.</span> <span class="toc-text">2.2.4 面试题 - 如何实现数组和 List 之间的转换</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#23-%E9%93%BE%E8%A1%A8"><span class="toc-number">3.3.</span> <span class="toc-text">2.3 链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#231-%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-number">3.3.1.</span> <span class="toc-text">2.3.1 单向链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#232-%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">3.3.2.</span> <span class="toc-text">2.3.2 单向链表时间复杂度分析</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#233-%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-number">3.3.3.</span> <span class="toc-text">2.3.3 双向链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#234-%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">3.3.4.</span> <span class="toc-text">2.3.4 双向链表时间复杂度分析</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#235-%E9%9D%A2%E8%AF%95%E9%A2%98-arraylist%E5%92%8Clinkedlist%E7%9A%84%E5%8C%BA%E5%88%AB%E6%98%AF%E4%BB%80%E4%B9%88"><span class="toc-number">3.3.5.</span> <span class="toc-text">2.3.5 面试题 - ArrayList 和 LinkedList 的区别是什么？</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-hashmap%E7%9B%B8%E5%85%B3%E9%9D%A2%E8%AF%95%E9%A2%98"><span class="toc-number">4.</span> <span class="toc-text">3 HashMap 相关面试题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#31-%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">4.1.</span> <span class="toc-text">3.1 二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#311-%E4%BA%8C%E5%8F%89%E6%A0%91%E6%A6%82%E8%BF%B0"><span class="toc-number">4.1.1.</span> <span class="toc-text">3.1.1 二叉树概述</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#312-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="toc-number">4.1.2.</span> <span class="toc-text">3.1.2 二叉搜索树</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#313-%E7%BA%A2%E9%BB%91%E6%A0%91"><span class="toc-number">4.1.3.</span> <span class="toc-text">3.1.3 红黑树</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#32-%E6%95%A3%E5%88%97%E8%A1%A8"><span class="toc-number">4.2.</span> <span class="toc-text">3.2 散列表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#321-%E6%95%A3%E5%88%97%E8%A1%A8hash-table%E6%A6%82%E8%BF%B0"><span class="toc-number">4.2.1.</span> <span class="toc-text">3.2.1 散列表（Hash Table）概述</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#322-%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0%E5%92%8C%E6%95%A3%E5%88%97%E5%86%B2%E7%AA%81"><span class="toc-number">4.2.2.</span> <span class="toc-text">3.2.2 散列函数和散列冲突</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#323-%E6%95%A3%E5%88%97%E5%86%B2%E7%AA%81-%E9%93%BE%E8%A1%A8%E6%B3%95%E6%8B%89%E9%93%BE"><span class="toc-number">4.2.3.</span> <span class="toc-text">3.2.3 散列冲突 - 链表法（拉链）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#324-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6-%E6%95%A3%E5%88%97%E8%A1%A8"><span class="toc-number">4.2.4.</span> <span class="toc-text">3.2.4 时间复杂度 - 散列表</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#33-%E9%9D%A2%E8%AF%95%E9%A2%98-%E8%AF%B4%E4%B8%80%E4%B8%8Bhashmap%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86"><span class="toc-number">4.3.</span> <span class="toc-text">3.3 面试题 - 说一下 HashMap 的实现原理？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#34-%E9%9D%A2%E8%AF%95%E9%A2%98-hashmap%E7%9A%84put%E6%96%B9%E6%B3%95%E7%9A%84%E5%85%B7%E4%BD%93%E6%B5%81%E7%A8%8B"><span class="toc-number">4.4.</span> <span class="toc-text">3.4 面试题 - HashMap 的 put 方法的具体流程</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#341-hashmap%E5%B8%B8%E8%A7%81%E5%B1%9E%E6%80%A7"><span class="toc-number">4.4.1.</span> <span class="toc-text">3.4.1 hashMap 常见属性</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#342-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90"><span class="toc-number">4.4.2.</span> <span class="toc-text">3.4.2 源码分析</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#35-%E9%9D%A2%E8%AF%95%E9%A2%98-%E8%AE%B2%E4%B8%80%E8%AE%B2hashmap%E7%9A%84%E6%89%A9%E5%AE%B9%E6%9C%BA%E5%88%B6"><span class="toc-number">4.5.</span> <span class="toc-text">3.5 面试题 - 讲一讲 HashMap 的扩容机制</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#36-%E9%9D%A2%E8%AF%95%E9%A2%98-hashmap%E7%9A%84%E5%AF%BB%E5%9D%80%E7%AE%97%E6%B3%95"><span class="toc-number">4.6.</span> <span class="toc-text">3.6 面试题 - hashMap 的寻址算法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#37-%E9%9D%A2%E8%AF%95%E9%A2%98-hashmap%E5%9C%A817%E6%83%85%E5%86%B5%E4%B8%8B%E7%9A%84%E5%A4%9A%E7%BA%BF%E7%A8%8B%E6%AD%BB%E5%BE%AA%E7%8E%AF%E9%97%AE%E9%A2%98"><span class="toc-number">4.7.</span> <span class="toc-text">3.7 面试题 - hashmap 在 1.7 情况下的多线程死循环问题</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#38-%E9%9D%A2%E8%AF%95%E9%A2%98-hashset%E4%B8%8Ehashmap%E7%9A%84%E5%8C%BA%E5%88%AB"><span class="toc-number">4.8.</span> <span class="toc-text">3.8 面试题 - HashSet 与 HashMap 的区别</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#39-%E9%9D%A2%E8%AF%95%E9%A2%98-hashtable%E4%B8%8Ehashmap%E7%9A%84%E5%8C%BA%E5%88%AB"><span class="toc-number">4.9.</span> <span class="toc-text">3.9 面试题 - HashTable 与 HashMap 的区别</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-%E7%9C%9F%E5%AE%9E%E9%9D%A2%E8%AF%95%E8%BF%98%E5%8E%9F"><span class="toc-number">5.</span> <span class="toc-text">3 真实面试还原</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#31-java%E5%B8%B8%E8%A7%81%E7%9A%84%E9%9B%86%E5%90%88%E7%B1%BB"><span class="toc-number">5.1.</span> <span class="toc-text">3.1 Java 常见的集合类</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#32-list"><span class="toc-number">5.2.</span> <span class="toc-text">3.2 List</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#34-hashmap"><span class="toc-number">5.3.</span> <span class="toc-text">3.4 HashMap</span></a></li></ol></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/interview/MySQL%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" rel="bookmark" title="Mysql相关面试题">Mysql相关面试题</a></li><li><a href="/interview/Redis%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" rel="bookmark" title="Redis相关面试题">Redis相关面试题</a></li><li><a href="/interview/Spring%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" rel="bookmark" title="Spring相关面试题">Spring相关面试题</a></li><li><a href="/interview/%E5%BE%AE%E6%9C%8D%E5%8A%A1%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" rel="bookmark" title="微服务相关面试题">微服务相关面试题</a></li><li><a href="/interview/%E6%B6%88%E6%81%AF%E4%B8%AD%E9%97%B4%E4%BB%B6%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" rel="bookmark" title="消息中间件相关面试题">消息中间件相关面试题</a></li><li class="active"><a href="/interview/Java%E9%9B%86%E5%90%88%E7%9B%B8%E5%85%B3%E9%9D%A2%E8%AF%95%E9%A2%98/" rel="bookmark" title="Java集合相关面试题">Java集合相关面试题</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope itemtype="http://schema.org/Person"><img class="image" itemprop="image" alt="anoxia" data-src="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/images/avatar.webp"><p class="name" itemprop="name">anoxia</p><div class="description" itemprop="description">anoxia的后端博客</div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">10</span> <span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">3</span> <span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">7</span> <span class="name">标签</span></a></div></nav><div class="social"><span class="exturl item github" data-url="aHR0cHM6Ly9naXRodWIuY29tL2xpbjB5dWFu" title="https:&#x2F;&#x2F;github.com&#x2F;lin0yuan"><i class="ic i-github"></i></span> <a href="/3102691553@qq.com" title="3102691553@qq.com" class="item email"><i class="ic i-envelope"></i></a></div><ul class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item"><a href="/about/" rel="section"><i class="ic i-user"></i>关于</a></li><li class="item dropdown"><a href="javascript:void(0);"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友達</a></li></ul></div></div></div><ul id="quick"><li class="prev pjax"></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/redis/" title="分类于 Redis">Redis</a></div><span><a href="/redis/%E8%AF%BB%E5%86%99%E4%B8%80%E8%87%B4%E9%97%AE%E9%A2%98/" title="关于缓存读写一致问题">关于缓存读写一致问题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/interview/" title="分类于 面经">面经</a></div><span><a href="/interview/%E6%B6%88%E6%81%AF%E4%B8%AD%E9%97%B4%E4%BB%B6%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" title="消息中间件相关面试题">消息中间件相关面试题</a></span></li><li class="item"><div class="breadcrumb"></div><span><a href="/HTTP%E5%92%8CWebsocket%E7%9A%84%E5%89%8D%E4%B8%96%E4%BB%8A%E7%94%9F/" title="HTTP和Websocket的前世今生">HTTP和Websocket的前世今生</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/interview/" title="分类于 面经">面经</a></div><span><a href="/interview/%E5%BE%AE%E6%9C%8D%E5%8A%A1%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" title="微服务相关面试题">微服务相关面试题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/interview/" title="分类于 面经">面经</a></div><span><a href="/interview/Java%E9%9B%86%E5%90%88%E7%9B%B8%E5%85%B3%E9%9D%A2%E8%AF%95%E9%A2%98/" title="Java集合相关面试题">Java集合相关面试题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/project/" title="分类于 项目总结">项目总结</a></div><span><a href="/project/Mysql%E6%A0%BC%E5%BC%8F%E8%BD%AC%E6%8D%A2/" title="连接数据库遇到问题">连接数据库遇到问题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/interview/" title="分类于 面经">面经</a></div><span><a href="/interview/Spring%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" title="Spring相关面试题">Spring相关面试题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/interview/" title="分类于 面经">面经</a></div><span><a href="/interview/MySQL%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" title="Mysql相关面试题">Mysql相关面试题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/interview/" title="分类于 面经">面经</a></div><span><a href="/interview/Redis%E9%9D%A2%E8%AF%95%E9%A2%98-%E5%8F%82%E8%80%83%E5%9B%9E%E7%AD%94/" title="Redis相关面试题">Redis相关面试题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/project/" title="分类于 项目总结">项目总结</a></div><span><a href="/project/bug%E9%97%AE%E9%A2%98%E5%8F%8A%E8%A7%A3%E5%86%B3/" title="项目常见问题">项目常见问题</a></span></li></ul></div><div><h2>最新评论</h2><ul class="leancloud-recent-comment"></ul></div></div><div class="status"><div class="copyright">&copy; <span itemprop="copyrightYear">2023</span> <span class="with-love"><i class="ic i-sakura rotate"></i> </span><span class="author" itemprop="copyrightHolder">anoxia @ 智慧笔记</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i> </span><span title="站点总字数">51k 字</span> <span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="ic i-coffee"></i> </span><span title="站点阅读时长">46 分钟</span></div><div class="powered-by">基于 <span class="exturl" data-url="aHR0cHM6Ly9oZXhvLmlv">Hexo</span> & Theme.<span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2FtZWhpbWUvaGV4by10aGVtZS1zaG9rYQ==">Shoka</span></div></div></div></footer></div><script data-config type="text/javascript">var LOCAL={path:"interview/Java集合相关面试题/",favicon:{show:"智慧笔记",hide:"别走嘛QwQ"},search:{placeholder:"文章搜索",empty:"关于 「 ${query} 」，什么也没搜到",stats:"${time} ms 内找到 ${hits} 条结果"},valine:!0,fancybox:!0,copyright:'复制成功，转载请遵守 <i class="ic i-creative-commons"></i>BY-NC-SA 协议。',ignores:[function(e){return e.includes("#")},function(e){return new RegExp(LOCAL.path+"$").test(e)}]}</script><script src="https://cdn.polyfill.io/v2/polyfill.js"></script><script src="//fastly.jsdelivr.net/combine/npm/pace-js@1.0.2/pace.min.js,npm/pjax@0.2.8/pjax.min.js,npm/whatwg-fetch@3.4.0/dist/fetch.umd.min.js,npm/animejs@3.2.0/lib/anime.min.js,npm/algoliasearch@4/dist/algoliasearch-lite.umd.js,npm/instantsearch.js@4/dist/instantsearch.production.min.js,npm/lozad@1/dist/lozad.min.js,npm/quicklink@2/dist/quicklink.umd.js"></script><script src="https://fastly.jsdelivr.net/ge/zero-yuan/zero-yuan@latest/js/app.js?v=0.2.5"></script></body></html><!-- rebuild by hexo-renderer-multi-next-markdown-it -->